package 每日一题;

import java.util.Arrays;

/**
 * 1043. 分隔数组以得到最大和
 * 给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
 * <p>
 * 返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [1,15,7,9,2,5,10], k = 3
 * 输出：84
 * 解释：数组变为 [15,15,15,9,10,10,10]
 * 示例 2：
 * <p>
 * 输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
 * 输出：83
 * 示例 3：
 * <p>
 * 输入：arr = [1], k = 1
 * 输出：1
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= arr.length <= 500
 * 0 <= arr[i] <= 109
 * 1 <= k <= arr.length
 */
public class D230419_T1043 {

    int[] dp;
    //深度递归 加记忆化搜索
    int K;
    int[] ARR;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        dp = new int[arr.length];
        K = k;
        Arrays.fill(dp, -1);
        ARR = arr;

        return dfs(arr.length - 1);
    }

    /**
     * 返回 以第i个元素为结尾的 分割数组最大和
     * <p>
     * 数组长度 8 k=3  arr[1,2,3,4,5,6,7,8]
     * <p>
     * { f(7)+1*max(8)
     * f(i) =  max {  f(6)+ 2* max(7,8)
     * { f(5) + 3*max(6,7,8)
     *
     * @param index 元素坐标
     * @return 最大和
     */
    public int dfs(int index) {

        if (dp[index] != -1) {
            return dp[index];
        }
        int res = 0;
        //
        if (index >= K) {

            //最后1到K个元素的最大值
            int maxEum = 0;

            for (int i = 1; i <= K; i++) {

                maxEum = Math.max(maxEum, ARR[index - i - 1]);
                res = Math.max(res, dfs(index - i) + i * maxEum);
            }
        } else {
            //数组长度 小于等于分割长度 直接找到最大值乘以数组长度 返回结果
            for (int i = 0; i <= index; i++) {
                res = Math.max(res, ARR[i]);
            }
            res = res * (index + 1);
        }
        dp[index] = res;
        return res;
    }

    public static void main(String[] args) {
        D230419_T1043 test = new D230419_T1043();
        int res = test.maxSumAfterPartitioning(new int[]{1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3}, 4);
    }

}
